package com.my.study.structures.sort;

import java.util.Arrays;

/**
 * @author Carlos
 * @version 1.0
 * @Description 希尔排序
 * <p>
 * 基本思想：把数据按下标的一定增量分组，对每组使用直接插入排序算法排序；
 * 随着增量减少，每组包含的关键字越来阅读，当增量减至1，整个文件被分成一组，排序完成
 * @date 2021/7/19 22:36
 **/
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};

//        swapSort(arr);

        insertSort(arr);
    }


    /**
     * 交换法，速度慢，不推荐使用！！！！
     *
     * @param arr
     */
    private static void stepSwapSort(int[] arr) {
        int temp = 0;

        //=========================第1轮排序
        // 第一轮排序，将10个数据分成5组
        for (int i = 5; i < arr.length; i++) {
            // 遍历各组中元素（5组，每组2个，[0,5]、[1,6]、[2,7]、[3,8]、[4,9]）
            for (int j = i - 5; j >= 0; j -= 5) {
                // 当前元素大于加上步长的元素，进行交换
                if (arr[j] > arr[j + 5]) {
                    temp = arr[j];
                    arr[j] = arr[j + 5];
                    arr[j + 5] = temp;
                }
            }
        }

        // {3, 5, 1, 6, 0, 8, 9, 4, 7, 2}
        System.out.println("希尔排序第1轮排序结果：" + Arrays.toString(arr));


        //=========================第2轮排序
        // 第二轮排序，将10个数据分成2组
        for (int i = 2; i < arr.length; i++) {
            // 遍历各组中元素（2组，每组5个，[3,1,0,9,7]、[5,6,8,4,2]）
            for (int j = i - 2; j >= 0; j -= 2) {
                // 当前元素大于加上步长的元素，进行交换
                if (arr[j] > arr[j + 2]) {
                    temp = arr[j];
                    arr[j] = arr[j + 2];
                    arr[j + 2] = temp;
                }
            }
        }

        // {0, 2, 1, 4, 3, 5, 7, 6, 9, 8}
        System.out.println("希尔排序第2轮排序结果：" + Arrays.toString(arr));

        //=========================第3轮排序
        // 第三轮排序，将10个数据分成1组
        for (int i = 1; i < arr.length; i++) {
            // 遍历各组中元素（2组，每组5个，[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]）
            for (int j = i - 1; j >= 0; j -= 1) {
                // 当前元素大于加上步长的元素，进行交换
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

        // {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
        System.out.println("希尔排序第3轮排序结果：" + Arrays.toString(arr));
    }

    private static void swapSort(int[] arr) {
        int temp = 0;
        for (int gap = arr.length; gap > 0 ; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    // 当前元素大于加上步长的元素，进行交换
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }

        System.out.println("希尔排序结果：" + Arrays.toString(arr));
    }


    /**
     * 移位法
     *
     * @param arr
     */
    private static void stepInsertSort(int[] arr) {



    }

    private static void insertSort(int[] arr) {
        for (int gap = arr.length; gap > 0 ; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int insertIndex = i;
                int insertVal = arr[insertIndex];

                if (insertVal < arr[insertIndex - gap]) {
                    while (insertIndex - gap >= 0 && insertVal < arr[insertIndex - gap]) {
                        arr[insertIndex] = arr[insertIndex - gap];
                        insertIndex -= gap;
                    }
                    arr[insertIndex] = insertVal;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

}
